From: "John F. Sowa" <sowa@bestweb.net>
Date: Fri, 12 Sep 2003 22:59:51 -0400
To: Tom Johnston <tjohnston@acm.org>


Tom,

I'd like to cite one of my favorite sources for the definition
of intension and extension, namely the first three pages of
Church's little book on the lambda calculus:

   http://www.jfsowa.com/logic/alonzo.htm
   The Calculi of Lambda Conversion

Church defines the distinction in terms of functions, but
you can generalize his definition to relations and other
mathematical structures.

He starts by defining a function as a rule, rather than
a set of tuples:

   A function is a rule of correspondence by which when anything
   is given (as argument) another thing (the value of the function
   for that argument) may be obtained. That is, a function is an
   operation which may be applied on one thing (the argument)
   to yield another thing (the value of the function).

I very much prefer this definition to the nominalistic definitions,
which identify a function (or relation) with a set of tuples.
Later, Church goes on to make what I believe is the clearest
and best definition of the distinction to be found in the 20th
century literature (in clarity and precision, it even rivals
the writings of Peirce and the medieval logicians):

   The foregoing discussion leaves it undetermined under what
   circumstances two functions shall be considered the same.

   The most immediate and, from some points of view, the best
   way to settle this question is to specify that two functions
   f and g are the same if they have the same range of arguments
   and, for every element a that belongs to this range, (fa) is
   the same as (ga). When this is done we shall say that we are
   dealing with functions in extension.

   It is possible, however, to allow two functions to be different
   on the ground that the rule of correspondence is different
   in meaning in the two cases although always yielding the same
   result when applied to any particular argument. When this is done
   we shall say that we are dealing with functions in intension.

   The notion of difference in meaning between two rules of
   correspondence is a vague one, but, in terms of some system of
   notation, it can be made exact In various ways. We shall not
   attempt to decide what is the true notion of difference in meaning
   but shall speak of functions in intension in any case where a
   more severe criterion of identity is adopted than for functions
   in extension. There is thus not one notion of function in intension,
   but many notions; involving various degrees of intensionality.

Then Church defines his version of the lambda calculus as a method
of defining one family of intensional definitions while leaving
open the possibility of having other, equally useful definitions
for other purposes:

   In the calculus of ?-conversion and the calculus of restricted
   ?-K-conversion, as developed below, It is possible, if desired,
   to interpret the expressions of the calculus as denoting functions
   in extension. However, in the calculus of ?-?-conversion, where
   the notion of identity of functions is introduced into the system
   by the symbol ?, it is necessary, in order to preserve the finitary
   character of the transformation rules, so to formulate these rules
   that an interpretation by functions in extension becomes impossible.
   The expressions which appear in the calculus of ?-?-conversion are
   interpretable as denoting functions in intension of an appropriate
   kind.

For such reasons, I object to identifying the intension of a relation
with the set of tuples:

TJ> My own thoughts about the difference between a row of a table
> (a tuple) and the table itself (a relation) is that the former is
> part of the extension of the relation, while the latter (more
> specifically, the set membership conditions which define it)
> represents the intension of the relation. Next, that one cannot
> always infer the intensional rules from the extensional instances
> because, at any given moment, the set of all those instances may
> not define the boundary conditions of all those rules.

This is one approach, but Church's definition is more general
because it allows the possibility of different intensional rules
for generating or selecting the elements of the set.

John

PS:  You might also like to see another of my favorite excerpts
from Church, which I copied from Cathy Legg's old web site:

   http://www.jfsowa.com/ontology/church.htm
   Alonzo Church on Women and Abstract Entities

PPS:  Note that Church uses the capital letter Sigma for the
existential quantifier in the lambda calculus.  That is Peirce's
notation, which is still used by logicians who want to have a
different kind of quantifier for one reason or another.  In his
famous paper on undecidability, Goedel uses Peirce's notation,
capital Pi, for the universal quantifier.

PPPS:  And if you have difficulties getting the Greek letters
to display properly, you are probably using an obsolete browser,
such as Internet Explorer.  Please upgrade to Mozilla, Opera,
or something more modern and less susceptible to viruses.